class Solution
{
public:
    int calculateMinimumHP(vector<vector<int>> &dungeon)
    {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> f(m + 1, vector<int>(n + 1, INT_MAX));
        // cout << m << ' ' << n << endl;
        // cout << f.size() << ' ' << f[0].size() << endl;
        // f[i][j]表示从[i,j]到终点需要的最小生命值
        // f[i][j] = min(f[i + 1][j], f[i][j + 1]) + (-f[i - 1][j - 1])
        f[m - 1][n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : 1 - dungeon[m - 1][n - 1];
        // cout << f[m][n] << endl;
        for (int i = m - 1; i >= 0; --i)
            for (int j = n - 1; j >= 0; --j)
            {
                if (i == m - 1 && j == n - 1)
                    f[i][j] = dungeon[m - 1][n - 1] >= 0 ? 1 : 1 - dungeon[m - 1][n - 1];
                else
                    f[i][j] = max(1, min(f[i + 1][j], f[i][j + 1]) - dungeon[i][j]);
                // cout << f[i][j] << endl;
            }
        return f[0][0];
    }
};